package org.jkuang.qstar.index.test.pc;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.jkuang.qstar.commons.io.FileOperator;

class Term {
	String word;
	int startoffset, pos;

	public Term(int startoffset, int pos, String word) {
		this.startoffset = startoffset;
		this.pos = pos;
		this.word = word;
	}

	public int endoffset() {
		return this.startoffset + word.length();
	}

	public int length() {
		return word.length();
	}

	public String toString() {
		return "start:" + startoffset + " pos:" + pos + " word:" + word;
	}
}

public class TreeAnalysis {
	private TNode root = new TNode((char) 0, false);
	boolean[] nodes = new boolean[64 * 1024];
	static final char ch0 = '\uFF00';
	static final char ch1 = '\uFF5F';

	public static void main(String[] args) throws IOException {

		String line = new FileOperator().readFile(new File("C:\\Users\\User\\Downloads\\highlight.txt"), "utf8");
		long tme = System.currentTimeMillis();
		for (int i = 0; i < 100; i++) {
			TreeAnalysis analysis = new TreeAnalysis();
			analysis.add("有限公司");
			analysis.find(line);
		}

		long end = System.currentTimeMillis();
		System.out.println("cost:" + (end - tme));

	}

	public List<Term> find(String str) {
		int start = 0;
		int length = str.length();
		str = str.toLowerCase();
		char[] values = str.toCharArray();
		List<Term> terms = new ArrayList<>();

		while (start < length) {
			char ch = values[start];
			// 全椒字符串换为半角字符
			ch = (char) (ch > ch0 && ch < ch1 ? ch - 65248 : ch);
			if (!nodes[ch]) {
				start++;
				continue;
			} else {
				int pos = root.find(values, start, -1);
				if (pos >= start) {
					terms.add(new Term(start, pos + 1, str.substring(start, pos + 1)));
					start = pos + 1;
				} else {
					start++;
				}
			}
		}
		return terms;
	}

	public void add(String str) {
		if (str == null || str.length() == 0) {
			return;
		}
		str = str.toLowerCase();
		nodes[(int) str.charAt(0)] = true;
		root.insert(str, 0);
	}

	private static class TNode implements Comparable<TNode> {
		// 标记当前节点是否是一个词的终止字符
		boolean mark;
		// 当前节点的字符
		char value;
		// 子节点
		TNode[] nodes;

		int nodesize;

		public TNode(char ch, boolean mark) {
			this.value = ch;
			this.mark = mark;
		}

		public int find(char[] chs, int nextPos, int leafoffset) {
			if (nextPos >= chs.length) {
				return -1;
			}
			int size = 0;
			char ch = chs[nextPos];
			// 全椒字符串换为半角字符
			ch = (char) (ch > ch0 && ch < ch1 ? ch - 65248 : ch);
			while (size < this.nodesize && nodes[size++].value < ch)
				;
			int pos = nodes[size - 1].value == ch ? size - 1 : -1;
			// int pos = index(chs[nextPos]);
			if (pos >= 0) {
				if (nodes[pos].mark) {
					leafoffset = nextPos;
					if (nodes[pos].nodesize == 0) {
						return nextPos;
					}
				}
				int next = nodes[pos].find(chs, nextPos + 1, leafoffset);
				return next > leafoffset ? next : leafoffset;

			} else {
				return -1;
			}
		}

		/*
		 * public int index(char ch) { if (this.nodesize < 5) { int size = 0; while
		 * (size < this.nodesize && nodes[size++].value < ch) ; return nodes[size -
		 * 1].value == ch ? size - 1 : -1; } else { return indexOf(nodes, this.nodesize,
		 * ch, Type._index); } }
		 */

		int indexOf(TNode[] nodes, int size, char node, Type type) {
			int fromIndex = 0;
			int toIndex = size - 1;
			while (fromIndex <= toIndex) {
				int mid = (fromIndex + toIndex) >> 1;
				int cmp = nodes[mid].compareTo(node);// this.comparator.compare(nodes[mid],
														// node);
				if (cmp < 0)
					fromIndex = mid + 1;
				else if (cmp > 0)
					toIndex = mid - 1;
				else
					return type == Type._insert ? -(mid + 1) : mid; // key
																	// found
			}
			switch (type) {
			case _insert:
				return fromIndex;
			case _index:
				return -(fromIndex + 1);
			default:
				return toIndex;
			}
		}

		public void insert(String str, int pos) {
			char ch = str.charAt(pos);
			boolean isleaf = pos == str.length() - 1;
			if (this.nodesize == 0) {
				nodes = new TNode[1];
				nodes[0] = new TNode(ch, isleaf);
				if (!isleaf) {
					nodes[0].insert(str, pos + 1);
				}
				this.nodesize++;
			} else {
				int _index = indexOf(nodes, nodesize, ch, Type._insert);
				if (_index >= 0) {
					int moved = this.nodesize - _index;
					if (this.nodesize == nodes.length) {
						nodes = Arrays.copyOf(nodes, nodes.length + 1);
					}
					if (moved > 0) {
						System.arraycopy(nodes, _index, nodes, _index + 1, moved);
					}
					nodes[_index] = new TNode(ch, isleaf);
					if (!isleaf) {
						nodes[_index].insert(str, pos + 1);
					}
					this.nodesize++;
				} else {
					if (isleaf) {
						nodes[0].mark = true;
					} else {
						nodes[-_index - 1].insert(str, pos + 1);
					}
				}
			}
		}

		@Override
		public int compareTo(TNode o) {
			if (this.value > o.value) {
				return 1;
			} else if (this.value < o.value) {
				return -1;
			}
			return 0;
		}

		public int compareTo(char o) {
			if (this.value > o) {
				return 1;
			} else if (this.value < o) {
				return -1;
			}
			return 0;
		}

		enum Type {
			_insert, _index
		}
	}
}